/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * https://leetcode.cn/problems/trapping-rain-water/
 * 思路：利用单调递减栈
 */
class TrapStack {
    public int trap(int[] height) {
        Deque<Integer> stack=new LinkedList<>();
        int len=height.length;
        int ans=0;
        for(int i=0;i<len;i++){
            while(!stack.isEmpty()&&height[i]>height[stack.peek()]){
                int top=stack.pop();
                if(stack.isEmpty()){
                    break;
                }
                int left=stack.peek();
                int curWidth=i-left-1;
                int curHeight=Math.min(height[left],height[i])-height[top];
                ans+=curWidth*curHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}